---
id: 5900f3cc1000cf542c50fede
title: '問題 95：友好的數鏈'
challengeType: 1
forumTopicId: 302212
dashedName: problem-95-amicable-chains
---

# --description--

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

有趣的是，220 的真因子之和爲 284，而 284 的真因子之和爲 220，形成了一條兩個數構成的鏈。 因此，220 和 284 被稱爲友好數對。

也許更長的鏈條鮮爲人知。 例如，從 12496 開始，可以形成一條五個數字的數鏈：

$$ 12496 → 14288 → 15472 → 14536 → 14264 \\,(→ 12496 → \cdots) $$

由於該鏈返回其起始點，因此稱爲友好數鏈。

找出最長友好數鏈中的最小數字，要求該鏈中的每一個數字均不能超過給定的 `limit`。

# --hints--

`amicableChains(300)` 應該返回一個數字。

```js
assert(typeof amicableChains(300) === 'number');
```

`amicableChains(300)` 應該返回 `220`。

```js
assert.strictEqual(amicableChains(300), 220);
```

`amicableChains(15000)` 應該返回 `220`。

```js
assert.strictEqual(amicableChains(15000), 220);
```

`amicableChains(100000)` 應該返回 `12496`。

```js
assert.strictEqual(amicableChains(100000), 12496);
```

`amicableChains(1000000)` 應該返回 `14316`。

```js
assert.strictEqual(amicableChains(1000000), 14316);
```

# --seed--

## --seed-contents--

```js
function amicableChains(limit) {

  return true;
}

amicableChains(300);
```

# --solutions--

```js
function amicableChains(limit) {
  function getSmallestMember(chain) {
    let smallest = chain[0];
    for (let i = 1; i < chain.length; i++) {
      if (smallest > chain[i]) {
        smallest = chain[i];
      }
    }
    return smallest;
  }

  function getFactorsSums(limit) {
    const factorsSums = new Array(limit + 1).fill(1);
    for (let i = 2; i <= limit / 2; i++) {
      for (let j = 2 * i; j <= limit; j += i) {
        factorsSums[j] += i;
      }
    }
    return factorsSums;
  }

  const factorsSums = getFactorsSums(limit);
  const checkedNumbers = new Set();

  let longestChain = 0;
  let smallestMember = 0;
  for (let i = 0; i <= limit; i++) {
    const curChain = [];
    let curNumber = i;
    while (!checkedNumbers.has(curNumber) && factorsSums[curNumber] <= limit) {
      curNumber = factorsSums[curNumber];

      const chainStart = curChain.indexOf(curNumber);
      if (chainStart === -1) {
        curChain.push(curNumber);
        continue;
      }

      const chainLength = curChain.length - chainStart;
      if (chainLength > longestChain) {
        longestChain = chainLength;
        smallestMember = getSmallestMember(curChain.slice(chainStart));
      }
      break;
    }

    for (let j = 0; j < curChain.length; j++) {
      checkedNumbers.add(curChain[j]);
    }
  }

  return smallestMember;
}
```
